package com.dyz.LeetCodeforSwordFingerOffer;

public class MaxSubArray42 {
    public static void main(String[] args) {

    }
    public int maxSubArray(int[] nums) {
        //动态规划
        // 新建动态规划数组
        int [] dp = new int [nums.length+1];
        // 由于下方遍历从1开始，先写入第一个数进dp[0]
        dp[0] = nums[0];
        // 设置最大值：由于最开始的是array[0]，后面如果是负数肯定更小，如果是整数肯定变大
        int maxValue = nums[0];
        for (int i= 1; i< nums.length; i++){
            dp[i] = Math.max(nums[i], dp[i-1]+nums[i]);
            if(dp[i]>maxValue){
                maxValue = dp[i];
            }

        }
        return maxValue;
    }
}
